home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / tutor / pro1 / chap13.doc < prev    next >
Text File  |  1990-07-19  |  13KB  |  282 lines
  1.  
  2.  
  3.  
  4.                                                                            129
  5.                         CHAPTER 13 - MULTIPLE WORD ARITHMETIC II
  6.  
  7.  
  8.              We have just done multiple word addition and subtraction, which
  9.              are easy. Now we have multiplication and division. We are going
  10.              to multiply and divide long numbers by a one word (2 byte)
  11.              number. Multiplying multiple-word numbers by multiple-word
  12.              numbers is complex and time consuming but can be done. Dividing
  13.              by a multiple-word number is an entirely different ballgame.{1}
  14.  
  15.              We'll do unsigned numbers first, then in a later chapter add the
  16.              code we need for signed numbers. The core routine is the same.
  17.  
  18.  
  19.              UNSIGNED MULTIPLICATION
  20.  
  21.              If you multiply an n digit number by an m digit number, there is
  22.              a possibility of n+m digits in the result. 863 is 3 digits, 4975
  23.              is 4 digits, 863 X 4975 = 4,293,425 is 7 digits = 4 + 3. We will
  24.              be multiplying an 8 byte number by a 2 byte number, so we'll need
  25.              10 bytes for the possible maximum result. Here's the code:
  26.  
  27.              ; - - - - - - - - ENTER DATA BELOW THIS LINE
  28.              multiplicand      dq    ?
  29.              multiplier        dw    ?
  30.              result            db    10 dup (?)
  31.  
  32.              ; - - - - - - - - ENTER DATA ABOVE THIS LINE
  33.  
  34.              ; - - - - - - - - ENTER CODE BELOW THIS LINE
  35.  
  36.              outer_loop:
  37.                  lea  ax, multiplicand    ; load multiplicand
  38.                  call get_unsigned_8byte
  39.                  call print_unsigned_8byte
  40.                  call get_unsigned        ; unsigned word to multiplier
  41.                  mov  multiplier, ax
  42.  
  43.  
  44.                  lea  si, multiplicand    ; load pointers
  45.                  lea  bx, result
  46.  
  47.                  mov  cx, 4          ; number of words
  48.                  sub  di,di          ; clear di 
  49.  
  50.              mult_loop:
  51.  
  52.              ____________________
  53.  
  54.                 1  For those of you with a hankering for large multiplication
  55.              and division, I have included subroutines which can multiply and
  56.              divide numbers of any length in a file called MISHMASH.DOC. It is
  57.              in \EXTRAFILE. You will need to finish all the chapters before
  58.              looking at it, since it uses things that you don't know about
  59.              yet.
  60.  
  61.              ______________________
  62.  
  63.              The PC Assembler Tutor - Copyright (C) 1989 Chuck Nelson
  64.  
  65.  
  66.  
  67.  
  68.              The PC Assembler Tutor                                        130
  69.              ______________________
  70.  
  71.                  mov  ax, [si]       ; multiplicand to ax
  72.                  mul  multiplier     ; {2}
  73.                  add  ax, di         ; high word from last multiplication
  74.                  jnc  store_result
  75.                  inc  dx             ; {3}
  76.              store_result:
  77.                  mov  [bx], ax       ; store 1 word of result.
  78.                  mov  di, dx         ; save high word for next multiplication
  79.                  add  si, 2          ; increment pointers
  80.                  add  bx, 2
  81.                  loop mult_loop
  82.  
  83.                  mov  [bx], di       ; move last word of result
  84.  
  85.                  mov  ax, [bx]
  86.                  call print_hex
  87.                  lea  ax, result
  88.                  call print_unsigned_8byte
  89.                  jmp  outer_loop
  90.  
  91.              ; - - - - - - - - ENTER CODE ABOVE THIS LINE
  92.  
  93.              There are two different input calls, an 8 byte one and a 2 byte
  94.              one. Inside the loop we store the high word from the
  95.              multiplication in DI and then add it to the next result. This is
  96.              the same as when you multiply single digits in base 10 (9 X 7 =
  97.              63 carry the 6). Note that when you add DI, there can be a carry
  98.              from AX to DX, but there can be no carry out of DX. After we drop
  99.              out of the loop, we need to put the last word in result. We take
  100.              it from DI, but we could take it from DX if we wanted. Finally,
  101.              the printing. Print_unsigned_8byte can't print the whole result,
  102.              so we are printing the high word in hex form. If those top two
  103.              bytes are non zero, what 'print_unsigned_8byte' prints will be
  104.              incorrect because it is missing the top 2 bytes. Note once again
  105.              that the only thing constraining this program to an 8 byte number
  106.              is the 4 that we put in CX - change that number and you can do
  107.              any size number that you want.
  108.  
  109.              Run a bunch of numbers through this, including a couple that have
  110.              more than a 20 digit result. 
  111.  
  112.  
  113.              UNSIGNED DIVISION
  114.  
  115.              Division is done the same way in the software as it is done with
  116.              pencil and paper, starting at the left and working right. On the
  117.              computer, this means starting with the high order word and
  118.              working down. 
  119.              ____________________
  120.  
  121.                 2 It would be about 3% faster to have this in a register, but
  122.              unfortunately we are out of registers.
  123.  
  124.                 3 Do we need to check DX for a carry here?  No. The maximum
  125.              multiplication is FFFFh X FFFFh. The result is FFFE 0001h. That
  126.              means that DX is a maximum FFFEh. If you add one, that's FFFFh,
  127.              and no carry occurs.
  128.  
  129.  
  130.  
  131.  
  132.              Chapter 13 - Multiple Word Arithmetic II                      131
  133.              ________________________________________
  134.  
  135.  
  136.              ; - - - - - - - - ENTER DATA BELOW THIS LINE
  137.              dividend    dq   ?
  138.              divisor     dw   ?
  139.              quotient    dq   ? 
  140.              remainder   dw   ?
  141.              ; - - - - - - - - ENTER DATA ABOVE THIS LINE
  142.  
  143.              ; - - - - - - - - ENTER CODE BELOW THIS LINE
  144.  
  145.              outer_loop:
  146.  
  147.                  lea  ax, dividend        ; get dividend
  148.                  call get_unsigned_8byte
  149.                  call print_unsigned_8byte
  150.                  call get_unsigned        ; get divisor
  151.                  mov  divisor, ax
  152.  
  153.                  lea  si, dividend + 6    ; start at the top
  154.                  lea  bx, quotient + 6
  155.                  mov  di, divisor
  156.                  mov  cx, 4               ; number of words
  157.                  sub  dx, dx              ; clear dx for first division
  158.  
  159.              division_loop:
  160.                  mov  ax, [si]            ; dividend word to ax
  161.                  div  di                  ; {4}
  162.                  mov  [bx], ax            ; word of result to quotient
  163.                  sub  si, 2               ; decrement the pointers
  164.                  sub  bx, 2
  165.                  loop division_loop
  166.  
  167.                  mov  remainder, dx
  168.                  mov  ax, remainder
  169.                  call print_unsigned
  170.                  lea  ax, quotient
  171.                  call print_unsigned_8byte
  172.  
  173.                  jmp  outer_loop
  174.  
  175.              ; - - - - - - - - ENTER CODE ABOVE THIS LINE
  176.  
  177.              That's it? Yup. The division instruction is designed to work
  178.              effeciently and simply. We start with the most significant
  179.              digits, divide, put the quotient in  the variable "quotient",
  180.              ____________________
  181.  
  182.                 4 After this division, the quotient is in AX and the remainder
  183.              is in DX. Say, aren't we going to do anything with the remainder?
  184.              There's nothing in the code about DX until we get out of the
  185.              loop. In fact, we ARE doing something with the remainder. Just
  186.              like division with pencil and paper, when you have a remainder,
  187.              you bring it down to the left of the next digits you are going to
  188.              divide. These get divided the next time around. But we don't need
  189.              to move the remainder because it's already in the right place.
  190.              Pretty snappy, huh? You don't need to move anything; it all takes
  191.              care of itself.
  192.  
  193.  
  194.  
  195.  
  196.              The PC Assembler Tutor                                        132
  197.              ______________________
  198.  
  199.              DECREMENT the pointers, and get the next word for division.
  200.              After the final division, we have the remainder left in DX, so we
  201.              move it to the variable "remainder". The final instructions print
  202.              the remainder and the quotient.
  203.  
  204.              Notice that we don't need to touch the remainder during the
  205.              entire operation. The 8086 leaves it exactly where it needs to be
  206.              for the next division. Using the DX register when you have single
  207.              word division seems screwy, but using DX for multiple word
  208.              division is both natural and elegant. The Intel people made one
  209.              instruction do the work of both. 
  210.  
  211.              Remember from the earlier chapter on division that you can get a
  212.              zero divide error if the quotient is larger than 65535. Is it
  213.              possible to get a quotient larger than 65535 in this routine? NO.
  214.              It is impossible to get a zero divide on anything other than a
  215.              zero.{5}
  216.  
  217.              Run the program and do several examples. You can even do a 0
  218.              divide if you feel like interrupting the program.
  219.  
  220.  
  221.              SIGNED NUMBERS
  222.  
  223.              For byte or word signed multiplication and division, the 8086
  224.              changes the signed numbers into unsigned numbers, does unsigned
  225.              multiplication/division, then adjusts for sign. For long numbers,
  226.              we have to do these operations ourselves, so we need three
  227.              sections of code. (1) change the numbers into unsigned numbers,
  228.              (2) do unsigned multiplication/division and (3) adjust the signs.
  229.              The routines that we have here are part two of this scheme. It
  230.              will be easier to implement this once you know about subroutines,
  231.              so signed division and multiplication will have to wait till
  232.              later.
  233.  
  234.  
  235.  
  236.              ____________________
  237.  
  238.                 5 This is technical, so if you start getting lost, don't worry
  239.              about it. How do we know that it's impossible?  What we are
  240.              putting in DX is the remainder (R). R is always less than the
  241.              divisor (D). Let Q be the number in AX the next time around. What
  242.              we are dividing is:
  243.                  ((R*65536) + Q ) / D  <= (( R*65536 ) + 65535 ) /D 
  244.              since Q is less than to or equal to 65535. This is the maximum.
  245.              ( ((R*(65535 + 1)) + 65535 ) /D = (((R+1) * 65535) + R)/D (huh?)
  246.                                           = ((R+1) * 65535)/D + R/D
  247.              Let's do a few examples: if D = 1, R < D so R = 0 max.
  248.                                 = (1*65535)/1 + 0/1 = 65535  rem 0
  249.              where rem = remainder. If D = 2, R < D so R = 1 max.
  250.                                 = ((1+1)*65535)/2 + 1/2 = 65535 rem 1
  251.              If D = 3, R < D so R = 2 max.
  252.                                 = (2+1)*65535)/3 + 2/3 = 65535 rem 2
  253.              See a pattern here? R/D < 1, so the quotient can never be 65536.
  254.              The maximum will always be 65535 with the remainder 1 less than
  255.              the divisor. If you aren't a techie, ignore all this.
  256.  
  257.  
  258.  
  259.  
  260.              Chapter 13 - Multiple Word Arithmetic II                      133
  261.              ________________________________________
  262.  
  263.                                      SUMMARY
  264.  
  265.  
  266.              For both signed and unsigned numbers, multiple word division and
  267.              multiplication are based on an unsigned number routine. Signed
  268.              numbers are changed into unsigned numbers, the operation is
  269.              performed, and the signs of the results are adjusted. 
  270.  
  271.  
  272.              Multiplication is done the same as for single words except that
  273.              the high word from one result is saved and added to the low word
  274.              of the next result, thus adding the two partial results. If this
  275.              addition gives a carry, DX must be incremented.
  276.  
  277.              Division operates from left to right. For the first division, DX
  278.              is zeroed. After that it always contains the remainder from the
  279.              last division. The quotients in AX are moved to memory one by
  280.              one. At the end, the final remainder will be in DX.
  281.  
  282.